package 链表;

import javafx.beans.binding.When;
import jdk.nashorn.internal.ir.WhileNode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class _206_反转链表 {
    //递归思想
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newNode = reverseList(head.next);

        head.next.next = head;
        head.next = null;
        return newNode;
    }

    //迭代思想 头插法
    public ListNode reverseList2(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            //tmp指向head的下一个节点(保证链表不断开)
            ListNode tmp = head.next;
            //head的下一个节点指向newHead
            head.next = newHead;
            //newHead指向head
            newHead = head;
            //将head指向下一个节点
            head = tmp;
        }
        return newHead;
    }


    /**
     * 链表逆序输出到动态数组中
     */
    List<Integer> list = new ArrayList<>();
    public List<Integer> reverseList3(ListNode head) {
      if (head!=null){
          reverseList3(head.next);

          list.add(head.val);
      }
        return list;
    }
}
